package 困难.脑筋急转弯;

import java.util.Arrays;

/**
 * 给定一个字符串 s 和一个整数 k 。你可以从 s 的前 k 个字母中选择一个，并把它加到字符串的末尾。
 * 返回 在应用上述步骤的任意数量的移动后，字典上最小的字符串 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/orderly-queue
 */
public class 有序队列_899 {

    public static void main(String[] args) {

        System.out.println(orderlyQueue("cba", 1));

    }

    /**
     * 当 k = 1 时，相当于一个环形字符串，假设字符串 s 的长度为 n
     * 那么以 s.charAt(i) 0<=i<=n-1 开头的字符串，为所有可能的字符串
     * 当 k > 1 时，总能够通过变化得到一个升序的字符串，即字典序最小的字符串
     * acsb
     * csba
     * sbac
     * sacb
     * acbs
     * absc
     * bsca
     * scab
     * sabc
     * abcs
     *
     * @param s
     * @param k
     * @return
     */
    public static String orderlyQueue(String s, int k) {
        if (k == 1) {
            String minStr = s;
            // 记录上一次的字符串，移动一次得到新的字符串
            StringBuilder preStr = new StringBuilder(s);
            for (int i = 1; i < minStr.length(); i++) {
                // 首位元素移动到末尾
                char one = preStr.charAt(0);
                preStr.deleteCharAt(0);
                preStr.append(one);
                if (preStr.toString().compareTo(minStr) < 0) {
                    minStr = preStr.toString();
                }
            }
            return minStr;
        } else {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            return new String(chars);
        }
    }

}
